\chapter[uvod_rozvrhovani]{Úvod do rozvrhování}
\section[rozvrhovani-data]{Základní pojmy}
V~této části se nejprve seznámíme s~pojmy Úloha a Zdroj jakožto
základními stavebními kameny rozvrhování. Poté bude uvedena jeho definice. Kritéria optimality budou zmíněna na konci této
sekce. Všechny tyto pojmy jsou dobře probrány například
v~\cite[ComplexScheduling,Blazewicz].
\subsection[rozvrhovani-uloha]{Úloha}
Úloha je základní prvek každého rozvrhovacího problému. Můžeme na ni
nahlížet jako na jednotku práce, kterou musíme nějakým způsobem
naplánovat k~provedení. Setkáváme se u~ní s~mnoha parametry, které může
mít.
\startitemize
	\item Doba vykonávání (processing time) $p_j$ 
	\item Začátek vykonávání (start time)  $s_j$ \footnote{Začátek
		vykonávání nemusí být jen jeden okamžik. Za předpokladu
			preemptivního rozvrhování může nastat situace,
			kdy je vykonávání úlohy přerušeno jinou úlohou a
	další pokračování úlohy považujeme za další okamžik začátku vykonávání.  }
	\item Konec vykonávání (completition time) $C_j$

	\item Okamžik disponability (release date) $r_j$ : Nejmenší čas,
	kdy je úloha připravena k~provedení.	
	\item Okamžik požadovaného dokončení (due date) $d_j$ : $C_j$ by
	měl být menší než tato hodnota. Pokud tomu tak není, může dojít k~penalizaci.
	\item Poslední okamžik dokončení (deadline) $\widetilde{d_j}$ :
	$C_j$ musí být menší než tento čas. Pokud se $C_j$ nevejde do
	stanoveného limitu, pak problém nemá řešení.
	\item Precedenční vazby na ostatní úlohy (precedence constraints): Velmi často dochází
k~situacím, kdy máme danou posloupnost úloh, které musí být
	vykonány v~daném pořadí. Tento fakt je nutné také zachytit ve
	vlastnostech úlohy.
	\item Stroj (dedicated processor): jeden a více strojů, na
					   kterých musí úloha běžet.
	\item Priorita (priority): důležitost úlohy v~porovnání s~ostatními. Použití nachází při~přesahování $d_j$,   kde je možné více penalizovat úlohy s~vyšší prioritou.
	\item Zpoždění (lateness) $L_j$ : $L_j = C_j - d_j$
	\item Doba čekání (waiting time) $w_j$ : $w_j = s_j - r_j$		    
	\item Překročení vymezeného času (tardiness) $D_j$ : $D_j = \max\{ C_j -d_j, 0\}$							    
	\item Doba dokončení (flow time, response time) $F_j$ : $F_j=C_j - r_j$ 
													     
\stopitemize
Parametry úlohy jsou na obrázku \in[fig:taskDef]. V~praxi se zřídka setkáme s~použitím všech parametrů úloh. Některé parametry se stejně dají vyjádřit pomocí ostatních -- není je tedy nutné při implementaci zahrnovat.
\placefigure[here, force][fig:taskDef]{Znázornění parametrů úlohy}
{\externalfigure[images/task-parameters.pdf]}

\subsection[rozvrhovani-zdroj]{Zdroj}
Jednotka, na které může být úloha vykonávána. Rozlišujeme zde mezi
zdroji, které mohou vykonávat pouze jednu úlohu v~čase -- unární zdroje (unary resources) a~zdroji, které mají jistou kapacitu prováděných úloh (limited capacity resources, cumulatives resources).
	U~zdrojů s~kapacitou vyšší než 1 se také setkáváme s~tzv.~\quotation{dávkovým} zpracováním úloh (batch processing).  To znamená, že několik úloh začíná ve stejný okamžik a dokud není připravená celá dávka úloh, čeká se~na~další úlohy do dávky.
Pod pojmem \quotation{zdroj} si v~teorii rozvrhování nemusíme
představovat
pouze stroj vyrábějící plošné spoje, montážního robota ve výrobně aut
nebo počítač (který řeší třeba distribuovaný program). Zdroji jsou:
\startitemize
	\item (Lidská) práce
	\item Peníze
	\item Energie
	\item Nástroje
	\item Stroje, roboti
\stopitemize
V~dalším pokračování budou považovány za zdroje jenom stroje.
\subsection[rozvrhovani-def]{Definice rozvrhování}
	Úkolem rozvrhování je alokovat množinu úloh $ {\cal T } = \{ T_1, T_2, \ldots , T_n \} $ na množinu dostupných strojů ${\cal P} = \{P_1, P_2, \ldots , P_m \} $ v~čase při dodržení všech omezujících podmínek (zde~navíc vzniká podmínka, že pokud je rozvrh nepreemptivní, pak žádná úloha nesmí být přerušena. Jinak může být přerušená právě konečným množstvím přerušení).   

V~praxi se setkáváme jednak s~tzv. statickým rozvrhováním, kde množina úloh je známá předem. To se uplatňuje většinou ve výrobních procesech (fabriky,
		dílny, školy). Druhou možností je dynamické
rozvrhování, kdy se množina úloh vyvíjí v~čase. To nachází uplatnění
naříklad v~robotice, kde robot v~jeden časový okomžik může provádět jednu množinu úloh a v~jiný časový okamžik jinou množinu úloh. Ale dopředu není jasné, které úlohy v~té množině budou.

Výsledek rozvrhování se většinou posuzuje vhodně zvolenou hodnotící funkcí.
Mohou to být například funkce $f (T_1, T_2, \ldots , T_n)$, které
vyjadřují :
\startitemize
\item Nejpozději dokončenou úlohu : $C_{max} = \max_{j=1}^{n}{\{C_j\}}$
\item Celkový součet všech dokončení úloh (total flow time): $ \displaystyle \sum_{j=1}^{n}{C_j}$
\item Vážený celkový součet všech dokončení úloh (weighted total flow
		time): $ \displaystyle \sum_{j=1}^{n}{w_jC_j}$
\item Maximální zpoždění: $L_{max}= \max_{j=0}^{n}{\{L_j\}}$
\item Součet překročení vymezeného času (tardiness): $\displaystyle  \sum_{j=1}^{n}{D_j}$
\item Vážený součet překročení vymezeného času:  $\displaystyle  \sum_{j=1}^{n}{w_jD_j}$
\item Vážený součet jednotkových penalizací $\displaystyle  \sum_{j=1}^{n}{w_jU_j}$, kde penalizace $U_j$ je definována jako: 
$ U_j= \cases{0 & pro $C_j<d_j$\cr 1 & jinak } $
\stopitemize
Nejmenší čas dokončení ještě neznamená nejlepší výsledek. Záleží na okolnostech
situace, pro kterou navrhujeme rozvrhovací algoritmus. Proto je důležité
si před vlastní implementací rozmyslet, kterou hodnotící funkci zvolit.
\footnote{Hodnotící funkce nemusí být jen právě jedna z~výše uvedených,
ale může to být i jejich kombinace. Případně to může být funkce, kterou navrhne
	ekonom pro minimalizaci nákladů apod. }


%\subsection[rozvrhovani-casova-omezeni]{Časová omezení}


\section[rozvrhovani-grahamovo_rozdeleni]{Grahamova notace}
V~praxi se setkáváme s~velkým množstvím různorodých rozvrhovacích
problémů. To~nás vede k~myšlence zavést standartní notaci. Grahamova
notace je velmi rozšířená a TORSCHE Scheduling toolbox s~ní pracuje
také. Proto tady ve stručnosti zmíním její hlavní rysy.

Základem je trojice položek 
\placeformula[eq:graham-notation]
\startformula
\alpha | \beta | \gamma
\stopformula


První položka $\alpha=\{\alpha_1,\alpha_2\}$ popisuje zdroje. $\alpha_1$
značí typ zdrojů (zda jsou stejné, předvolené), $\alpha_2$ popisuje
jejich počet. 

Druhé pole $\beta$ v~sobě nese informaci o~vlastnostech problému jako
takového (preempce, precedenční vazby, doby trvání jednotlivých úloh,
		deadline apod.)


$\gamma$ udává optimalizační kritérium (podsekce \in[rozvrhovani-def])


Podrobněji pojednává o~Grahamově notaci například \cite[Blazewicz]  


%%%%-----------------------GANT DIAGRAMS----------------%%%%%%%%%%%%5

\useexternalfigure
  [GANTT][images/gantt-3tasks.pdf]
  [width=.5\textwidth]
\useexternalfigure
  [TON][images/taskOnNode.pdf]
  [width=.5\textwidth]
\useexternalfigure
  [TOA][images/taskOnArc.pdf]
  [width=.5\textwidth]



\section[rozvrhovani-Ganttovy-diag]{Grafické znázornění problému}
Pro lepší a rychlejší pochopení zadání nebo výsledku je vhodné zobrazit celý problém pomocí diagramu.
Pro zadání se používají {\it task-on-node} nebo {\it task-on-arc} grafy.
Jak už název napovídá, u~prvního jmenovaného jsou úlohy umístěny na
vrcholech grafu zatímco u~druhého na hranách grafu. Vše je přehledně
vidět na obrázku \in[fig:TON_TOA], který vystihuje zadání podle zápisu
\in[eq:zadani_TOA_TON]. Binární operátor $\rightarrow$ představuje precedenční vazbu mezi úlohami. V~tomto případě $T_2$ musí být provedena před $T_3$.
\placeformula[eq:zadani_TOA_TON]
\startformula
{\cal T} = \{T_1, T_2, T_3 \}\mbox{, } p_1=6\mbox{, }p_2=4\mbox{, }p_3=1  \mbox{, } T_2 \rightarrow T_3 
\stopformula
\input images/metapost/taskOnArc.tex
\placefigure
  [here,force]
  [fig:TON_TOA]
  {Dva zůsoby zobrazení zadání rozvrhovacího problému s~precedenčními vazbami.}
{\startcombination[2*1]
    {\FLOWchart[taskOnArc]}   {Task-on-arc graf - hrany reprezentují
				     úlohy.}
    {\externalfigure[TON]} {Task-on-node graf - vrcholy reprezentují
				   úlohy.}
  \stopcombination
}

U~Task-on-node  grafů se setkáme s~dvojí možností zakreslení. Jednak se všemi úlohami a precedenčními vazbami mezi nimi (např v~\cite[Blazewicz], v~obrázku zakresleny pouze plnou čarou a vrcholy pouze s~okrajem), ale také se můžeme setkat se situací, kdy se do grafu přidávají dvě \quotation{nadbytečné} úlohy,
	které mají nulový čas vykonávání a jsou umístěny jako počáteční
	resp. koncová úloha. Ty~se~využívají k~vymezení časového
	úseku od začátku skutečné první úlohy do~konce poslední skutečné
	úlohy. (např v~\cite[ComplexScheduling], v~obrázku hrany
			čárkovaně a vrcholy bez okrajů).
\startfiguretext
[right]
  [fig:gantt]
{Ganttův diagram\footnote{ Původním názvem byl vlastně jen {\it Harmonogram}, jehož autorem byl Karol Adamiecky. Ale ten svoje dílo po dlouhou dobu neprezentoval a proto se uchytilo pojmenování po Henry Ganttovi. } vygenerovaný pomocí
				       funkce {\tt plot} v~TORSCHE
						       toolboxu, viz
						       \cite[TORSCHE]}
    {\externalfigure[GANTT]}


K~zobrazení výsledného rozvrhu se velmi často používají Ganttovy diagramy. Ty jsou známé spíše z~manažerské oblasti, kde se často používají pro plánování projektů. V~podstatě jde o~sloupcový graf, který nese úplnou informaci o~jednotlivých úlohách (začátek, konec, precedence, zdroj). Podrobněji o~nich pojednává \cite[GanttChart].

Hlavní rysy obou vystihuje obrázek \in[fig:gantt], který
představuje řešení rozvrhovacího problému zadaného zápisem
\in[eq:zadani_TOA_TON].
\stopfiguretext


%t1 =task('T1',6)
% t2 =task('T2',4)
% t3 =task('T3',1)
% T = [t1 t2 t3]
%T = taskset(T,[0 0 0; 0 0 0; 0 1 0])
%plot(T)
%
%t2=task('T2',4,1, 14)
%t1=task('T1',3,5, 10)
%T = [t1 t2]
%T = taskset(T,[0 0 ; 1 0])
% plot(T)



%%%%%%----------SHOP-----------%

\section[rozvrhovani-shopy]{Problémy rozvrhování v~dílně}
Dílna je místo, kde je vytvářen nějaký produkt. Proces
výroby se může skládat z~několika operací, které se vykonávají na strojích
v~dílně umístěných. Je-li dělníků v~dílně více, pak může  nastat situace, kdy jeden dělník čeká na dokončení práce jeho kolegy na
stroji, který chce využívat. Řešením celé situace může být vhodnější
naplánování provádění úloh, aby nedocházelo k~podobným situacím a tím se
uspořil čas i peníze.

%	Představte si dílnu, kde se vyrábí nějaký větší produkt. Dělník pobíhá většinou mezi
%jednotlivými stroji, kde každý z nich je dobrý právě na tu danou práci a
%na jinou ne. Jistě se~snaží minimalizovat čas nebo náklady dobrým
%využíváním strojů. 

Právě takto se v~rozvrhování chápou problémy dílen. V~dalším pokračování
budu nazývat tento problém \quotation{shopem}\footnote{Terminologie teorie
	rozvrhování má v~českém jazyce ještě rezervy a většinou se
		používají slova přejatá z~angličtiny. Je to především
		proto, že není rozšířená literatura psaná v~českém
			jazyce pojednávající o~tomto tématu.}.
Základní stavební jednotkou shopu je job, který se skládá z~množiny úloh. ${\cal{J}}_i=\{T_{i1}, T_{i2},
	\ldots , T_{in} \}$. Každá z~úloh $T_{ij} \in {\cal{J}}_i$ má svůj stroj,
		na kterém poběží $\mu_{ij}\in \{P_1, P_2, \ldots , P_m \}$. V~obecném shopu platí následující podmínky:
	\startitemize
		\item  Žádné dvě úlohy z~jednoho jobu neběží současně. 
		\item  Každý stroj zvládá v~daném okamžiku zpracovávat
		pouze jednu úlohu (u~rozšíření obecného shopu tato
				podmínka nemusí platit -- některé stroje
				mohou mít kapacitu vyšší než 1. Více
o~tom pojednává kapitola \in[ooa])
		\item V~shopech se vyskytují precedenční omezení, která
		musí být splněna.
	\stopitemize
O~třech základních shopech budou pojednávat další podsekce. Jejich základní
znaky lze pozorovat na obrázku \in[fig:shops], který zobrazuje jejich Ganttovy diagramy. O~shopech se lze dočíst například v~\cite[Blazewicz,Pinedo-theory,ComplexScheduling].
\subsection[rozvrhovani-jobshop]{Job-shop}
Job-shop rozšiřuje obecný shop o~sadu precedenčních omezení, které
vnucují pořadí úloh $T_{ij} \in {\cal J}_i$ do řetězce.
\placeformula[eq:job]
\startformula
T_{i1} \rightarrow T_{i2} \rightarrow \ldots \rightarrow T_{in}
\stopformula
To znamená, že se zde nevyskytují jakékoliv precedence mezi úlohami
v~jednotlivých jobech, ale pouze vrámci jobu. 

Zadání pro jobshop se dá vyjádřit ve tvaru dvou matic. Matice doby
	trvání úloh $T$ a matice strojů $P$, na kterých úlohy poběží.
%\startformula 
% {T}  = \left[ \matrix{p({\cal J}_1) \cr p({\cal J}_2)} \right]  = \left[\matrix{ p(T_{11}) & p(T_{12})  \cr p(T_{21}) & p(T_{22}) \cr} \right]  = \left[\matrix{ 1 & 3  \cr 2 & 4 \cr} \right]\mbox{ , } {P} = \left[ \matrix{\mu_{11} & \mu{12} \cr \mu_{21} & \mu_{22}\cr} \right]  =\left[\matrix{ 2 & 1 \cr  1& 2 \cr} \right] 
%\stopformula
\placeformula \startformula \startalign[n=4]
\NC  {T} \NC = \left[ \matrix{p({\cal J}_1) \cr p({\cal J}_2)} \right] \NC = \left[\matrix{ p(T_{11}) & p(T_{12})  \cr p(T_{21}) & p(T_{22}) \cr} \right] \NC = \left[\matrix{ 1 & 3  \cr 2 & 4 \cr} \right]  \NR[eq:vstupjobShopu]
\NC {P}\NC = \left[ \matrix{\mu_{11} & \mu_{12} \cr \mu_{21} & \mu_{22}\cr} \right] \NC =\left[\matrix{ 2 & 1 \cr  1& 2 \cr} \right] \NC  \NR 
\stopalign \stopformula

\subsection[rozvrhovani-flowshop]{Flow-shop}
Flow-shop je zvláštní případ Job-shopu, kde j-té úlohy v~jednotlivých
jobech běží na stejných strojích. V~případě platnosti $\mu_{ij}=j$ stačí k~zadání problému pouze
matice $T$ z~(\in[eq:vstupjobShopu]).

\subsection[rozvrhovani-openhop]{Open-shop}
{Slovo \quotation{Open} už napovídá, že jednotlivé úlohy v~jobech nebudou
mít žádné precedenční vazby. V~ostatním se shoduje s~Flow-shopem.
}



\useexternalfigure
  [OPENSHOP][images/openshop-example.pdf]
  [width=.5\textwidth]
\useexternalfigure
  [FLOWSHOP][images/flowshop-example.pdf]
  [width=.5\textwidth]
\useexternalfigure
  [JOBSHOP][images/jobshop-example.pdf]
  [width=.5\textwidth]
 \setupcombinations[]
\midaligned{
\placefigure
  []
  [fig:shops]
  {Rozvrhy pro Job-shop, Flow-shop a Open-shop zadané maticí (\in[eq:vstupjobShopu]).}
{\startcombination[2*1]
    {\externalfigure[JOBSHOP]}{Job-shop}
     {\externalfigure[FLOWSHOP]} {Flow-shop}

   \midaligned{{\externalfigure[OPENSHOP]}} {\midaligned{Open-shop}}
  \stopcombination
}
}
%Jobshop:
%t12 = task('T12',3,2,10,10,1,1)
%t22 = task('T22',4,2,10,10,1,2)
%t21 = task('T21',2,0,10,10,1,1)
%t11 = task('T11',1,0,10,10,1,2)
%plot(taskset([t11 t12 t21 t22],[0 0 0 0; 1 0 0 0; 0 0 0 0; 0 0 1 0]),'Prec',1,'Proc',1,'Axis',[0 8])
%
%OpenShop:
%t12 = task('T12',3,0,10,10,1,1)
%t22 = task('T22',4,0,10,10,1,2)
%t11 = task('T11',1,4,10,10,1,2)
%t21 = task('T21',2,3,10,10,1,1)
%plot([t11 t12 t21 t22],'Prec',1,'Proc',1,'Axis',[0 8])
%
%Flow-shop
%t11 = task('T11',1,0,10,10,1,1)
%t12 = task('T12',3,1,10,10,1,2)
% t21 = task('T21',2,1,10,10,1,1)
%t22 = task('T22',4,4,10,10,1,2)	
%plot([t11 t12 t21 t22],'Proc',1,'Axis',[0 8])






